10006. Числа Кармайкла

Малая теорема Ферма утверждает, что если n – простое число, то для любого a Î [2, n – 1] имеет место равенство:

aⁿ mod n = a

Числами Кармайкла называются такие составные числа, которые удовлетворяют теореме Ферма для всякого a Î [2, n – 1], то есть ведут себя как простые числа.

Для заданного входного числа n следует проверить, является ли оно числом Кармайкла.

Вход. В каждой строке находится натуральное число n, 2 < n < 65000. Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого входного n вывести сообщение, является ли оно числом Кармайкла в соответствии с приведенным ниже форматом.

Пример входа

1729

17

561

1109

431

0

Пример выхода

The number 1729 is a Carmichael number.

17 is normal.

The number 561 is a Carmichael number.

1109 is normal.

431 is normal.

РЕШЕНИЕ

теория чисел, предвычисление

Анализ алгоритма

Найдем все числа Кармайкла, меньшие 65000 и запомним их в массиве. Далее для каждого тестируемого n проверям, содержится ли оно в массиве или нет.

Реализация алгоритма

Занесем в массив carm все числа Кармайкла, меньшие 65000. Таких чисел будет 16.

int n, i, carm[] = {561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841,

29341, 41041, 46657, 52633, 62745, 63973, 75361};

Для каждого входного n проверим, встречается ли оно в массиве carm. Если встречается, то оно является числом Кармайкла. Иначе – нет.

while(scanf("%d",&n),n)

{

for(i = 0; i < 16; i++)

if (n == carm[i]) break;

if (i < 16) printf("The number %d is a Carmichael number.\n",n);

else printf("%d is normal.\n",n);

}